package com.jxb.three;

import java.util.HashMap;

import com.jxb.first.ListNode;

/**
 * 类注释
 *
 * @author jiaobo
 * @date Created in 2024/12/29 20:15
 **/
public class LRUCache_146 {

    private HashMap<Integer, LinkedNode> cache = new HashMap<Integer, LinkedNode>();
    /*链表的头尾指针结点，不存放实际业务数据*/
    private LinkedNode head, tail;

    class LinkedNode {
        int key;
        int value;
        LinkedNode pre;
        LinkedNode next;
    }

    //头插法
    private void addNode(LinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    /*将结点从链表摘除*/
    private void removeNode(LinkedNode node){
        LinkedNode pre = node.pre;
        LinkedNode post = node.next;
        pre.next = post;
        post.pre = pre;
    }

    /*将结点移动到头部*/
    private void moveToHead(LinkedNode node){
        this.removeNode(node);
        this.addNode(node);
    }

    /*移除尾部结点*/
    private LinkedNode removeTail(){
        LinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }

    class LRUCache {

        private ListNode listNode;

        private int capacity;

        public LRUCache(int capacity) {
            head = new LinkedNode();
            head.key = capacity;
            head.value = 0;
            tail = new LinkedNode();
            tail.next = null;
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            LinkedNode node = cache.get(key);
            if (node == null) {
                return -1;
            }
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            LinkedNode node = cache.get(key);
            if (node == null) {
                LinkedNode newNode = new LinkedNode();
                newNode.key = key;
                newNode.value = value;
                cache.put(key,newNode);
                addNode(newNode);
                ++head.value;
                if (head.value > head.key) {
                    //超出了容量限制，移除尾节点
                    LinkedNode tail = removeTail();
                    cache.remove(tail.key);
                    --head.value;
                }
            }else {
                node.value = value;
                moveToHead(node);
            }
        }
    }

}
